#include <iostream>
using namespace std;

#define MAX 50

int M[MAX][MAX];  // 路径矩阵
int dp[MAX][MAX]; // 动规矩阵，dp[i][j]表示到达(i,j)的最短路径长度
int m, n;         // m行，n列

// 递推公式
// dp[i][j] = min(dp[i-1][j],dp[i][j-1])+map[i][j]
// 特别的，当i=0时，只能从左上角向下得到；当j=0时，只能从左上角向右得到
int min_path()
{
    int i, j;
    dp[0][0] = M[0][0];
    // 第一列元素
    for (i = 1; i < n; i++)
        dp[i][0] = M[i][0] + dp[i - 1][0];

    // 第一行元素
    for (j = 1; j < m; j++)
        dp[0][j] = M[0][j] + dp[0][j - 1];

    // 按照递推公式求所有点
    for (i = 1; i < n; i++)
        for (j = 1; j < m; j++)
            dp[i][j] = M[i][j] + (dp[i - 1][j] < dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1]);

    return dp[n - 1][m - 1];
}

int main()
{
    memset(dp, 0, sizeof(int) * MAX * MAX);
    cout << "请输入矩阵大小m行，n列：";
    cin >> m >> n;
    cout << "请输入" << m << "行，" << n << "列的图矩阵:" << endl;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            cin >> M[i][j];

    cout << "从左上角到右下角最短路径为：" << min_path() << endl;

    return 0;
}

/*
请输入矩阵大小m行，n列：
4 4
请输入4行，4列的图矩阵：
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
*/